package model;
@SuppressWarnings("unchecked")
public class HeapSort extends Sorter {
    
	private static Comparable[] a;
    private static int n;

    HeapSort(){
	super();
	statistics = new Statistics();
    }
    
    private void heapsort()
    {
        buildheap();
        while (n>1)
        {
            n--;
            exchange (0, n);
            downheap (0);
        } 
    }

    private void buildheap()
    {
        for (int v=n/2-1; v>=0; v--)
            downheap (v);
    }

    private void downheap(int v)
    {
        int w=2*v+1;    // first descendant of v
        while (w<n)
        {	
            //check
            statistics.incrementChecks();
            
            if (w+1<n){    // is there a second descendant?
                if (a[w+1].compareTo(a[w])>0) w++;
            // w is the descendant of v with maximum label
                statistics.incrementChecks();
            }

            if (a[v].compareTo(a[w])>=0) return;  // v has heap property
            // otherwise
            exchange(v, w);  // exchange labels of v and w
            v=w;        // continue
            w=2*v+1;
        }
    }

    private void exchange(int i, int j)
    {	
	//Swap
	statistics.incrementSwaps();
	if(simulation)
	    PushSwapToQueue(i, j);
	
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    

	@Override
	public void sort(Comparable[] workArray) {
	    	a=workArray;
	        n=a.length;
	        long beforeTime = System.nanoTime();
	        
	        heapsort();
	        
	        long afterTime = System.nanoTime();
	        statistics.setRunTime(afterTime - beforeTime);
	}

	@Override
	public int getComplexity(int arraySize) {
	    return (int) (Math.pow(arraySize, 2) * .5);
	}

}
